\chapter{Preliminaries} \label{chap:prel}
\lettrine[lines=3]{T}{his}
chapter presents preliminaries related to models and theory for
control applications and their underlying distributed execution
platform. We shall also introduce notation that is common for the
remainder of this thesis.  In Section~\ref{prel:sec:controlprelim}, we
shall discuss control design, modeling, and performance.  Further, we
present the application and platform model in
Section~\ref{prel:sec:sysmodel}.


% CONTROLLER DESIGN
\section{Control Model and Design} \label{prel:sec:controlprelim}
In this section, we shall introduce the plant and disturbance models
to be considered throughout this thesis. We continue with a discussion
of the structure and performance of a feedback-control loop,
including a physical plant and a controller implementation. The
section ends with a discussion of controller synthesis in relation to
the introduced metric of control performance.

\begin{figure}
  \centering
  \includegraphics[width=0.8\textwidth]{controlscheduling/figures/figs/controllerblockdiag}
  \caption[Structure of a feedback-control loop comprising a controller
   and the physical plant to be controlled]
   {Structure of a feedback-control loop comprising a
    controller and the physical plant to be controlled. The controller
    communicates with sensors and actuators to implement a state
    observer and a state-feedback component.}
  \label{prel:fig:controllerblockdiag}
\end{figure}

\subsection{Feedback-Control Loop} \label{prel:sec:controlloop}
\Figref{prel:fig:controllerblockdiag} shows a block diagram of a
typical feedback-control loop, including a controller and a plant, or
physical process, to be controlled.  The control problem is to
control the state $\plantstate$\newnot{symbol:plantstate} of the plant
to the desired state $\plantstate_\textrm{d}$ in the presence of
continuous disturbances $\disturbance$ acting on the plant. Sensors
are connected to the plant in order to measure its outputs. These
measurements, including measurement errors of the sensors, are inputs
to the controller block, depicted in
\Figref{prel:fig:controllerblockdiag} with a dashed rectangle. 
\cbstart
In practice, it is not possible to measure all plant states.  Therefore,
the controller includes an observer component that produces an
estimate $\estimate{\plantstate}$ of the plant state, based on the
measured plant outputs $\plantoutput$.\newnot{symbol:plantoutput}
The feedback-gain block, denoted with $L$ in
the figure, computes the control signal
$\plantinput$\newnot{symbol:plantinput} to be actuated based on the
estimated error $\plantstate_\textrm{d} - \estimate{\plantstate}$.
\cbend
The dashed rectangle in \Figref{prel:fig:controllerblockdiag} thus
shows the control law
\begin{displaymath}
\plantinput : \mathbb{R}^{n_{\plantoutput}}
\longrightarrow \mathbb{R}^{n_{\plantinput}},
\end{displaymath}
where $n_{\plantoutput}$ and $n_{\plantinput}$, respectively, are the
number of measured plant outputs and the number of control signals
applied to the plant. We shall in the continuation, depending on the
context, use the notation $\plantinput$ to refer to the control law
and to refer to the actual plant input as well. 
When $\plantinput$ is used to denote the plant input, it is a function
of time
\begin{displaymath}
\plantinput : [0,\infty)
\longrightarrow \mathbb{R}^{n_{\plantinput}}.
\end{displaymath}

\cbstart
The desired state $\plantstate_\textrm{d}$ is typically
given or is computed by a separate control component based on
reference signals and the model of the controlled plant. 
In the continuation, without loss of generality for the linear
time-invariant systems considered in this thesis, we shall consider
$\plantstate_\textrm{d} = 0$; the plant model is described in
Section~\ref{prel:sec:plantmodel}. 
\cbend
In addition to state feedback, control applications can include additive
feedforward information in the control signal. Feedforward is
typically used to reduce measurable disturbances or to improve
response to command signals.  The feedback and feedforward components
are usually designed separately and are evaluated against different
performance metrics.


Control applications are typically implemented as periodic activities
comprising computation and communication. Thus, a controller of a
plant is characterized by a sampling period and a control law. Periodic
implementations are very common in most embedded control systems
(adaptive, event-based control strategies are emerging in application
domains in which computation and communication resources are very
limited~\cite{astrom07eventbased}; this is the topic of
Chapter~\ref{chap:selftriggered}). The controller is implemented by
one or several tasks that sample and process the plant outputs
$\plantoutput$ periodically, and subsequently compute and update the
control signal $\plantinput$ according to the control law.


\subsection{Plant Model} \label{prel:sec:plantmodel}
Throughout this thesis, we shall denote the set of plants to be
controlled by $\plants$\newnot{symbol:plantset}. Let us also introduce
its index set $\indexset_\plants$\newnot{symbol:indexsetplants}. The
synthesis problem is to construct controllers (periods and control
laws) and to accommodate these on a given execution platform.  Each
plant $\plant_i$\newnot{symbol:planti} ($i \in \indexset_\plants$) is
modeled as a continuous-time linear system~\cite{astrom97}.
Specifically, this model is given by a set of differential equations
\begin{equation}
  \timederivative{\plantstate}_i(t) = A_i \plantstate_i(t) + B_i \plantinput_i(t) + \disturbance_i(t),
  \label{prel:eq:plantdynamics}
\end{equation}
where the vector functions of time
$\plantstate_i$\newnot{symbol:plantstatei}
and $\plantinput_i$\newnot{symbol:plantinputi} are the plant state and
controlled input, respectively, and the vector $\disturbance_i$ models
plant disturbance as a continuous-time white-noise process with given
variance $R_{1i}$.  The matrices $A_i$ and $B_i$ model how the plant
state evolves in time depending on the current plant state and
provided control input, respectively. 
\cbstart
Typically, not all plant states
can be measured by the available sensors.
\cbend
The measurable plant
outputs are denoted with $\plantoutput_i$ and are modeled as
\begin{equation}
  \plantoutput_i(t) = C_i \plantstate_i(t) + \measnoise_i(t),
  \label{prel:eq:plantoutputs}
\end{equation}
where $\measnoise_i$ is an additive measurement noise.  The
continuous-time output~$\plantoutput_i$\newnot{symbol:plantoutputi} is
measured and sampled periodically and is used to produce the control
signal~$\plantinput_i$. The matrix $C_i$, which often is diagonal,
indicates those plant states that can be measured by available
physical sensors. If all states can be measured, the matrix $C_i$ is
the identity matrix and the linear model is only given by
Equation~\ref{prel:eq:plantdynamics}. Because the plant outputs are
sampled at discrete time instants, the measurement
noise~$\measnoise_i$ is modeled as a discrete-time white-noise process
with variance~$R_{2i}$. The control signal is actuated at discrete
time instants and is held constant between two updates by a hold
circuit in the actuator~\cite{astrom97}.

As an example of a system with two plants, let us consider a set of
two inverted pendulums~$\plants = \{\plant_1,
\plant_2\}$. Each pendulum $\plant_i$ ($i \in \indexset_\plants =
\{1,2\}$) is modeled according to Equations~\ref{prel:eq:plantdynamics}
and~\ref{prel:eq:plantoutputs}, with
\begin{displaymath}
A_i = {\left[ \begin{array}{cc}
    0 & 1\\
    g/l_i & 0
  \end{array} \right]},
\end{displaymath}
\begin{displaymath}
B_i = \left[ \begin{array}{c}
  0 \\
  g/l_i
\end{array} \right],
\end{displaymath}
and
\begin{displaymath}
C_i = \left[ \begin{array}{cc}
    1 & 0 \end{array} \right],
\end{displaymath}
where $g \approx 9.81$~$\textrm{m}/\textrm{s}^2$ and~$l_i$ are the
gravitational constant and length of pendulum~$\plant_i$, respectively
($l_1 = 0.2$~m and~$l_2 = 0.1$~m). The two states are the pendulum
position and speed. For the plant disturbance and
measurement noise we have $R_{1i} = B_i \transpose{B_i}$ and $R_{2i} =
0.1$. The inverted pendulum model appears often in
literature as an example of control problems for unstable processes.




\subsection{Control Quality} \label{prel:sec:controlperformance}
Considering one of the controlled plants $\plant_i$ in isolation, the
goal is to control the plant states in the presence of the additive
plant disturbance $\disturbance_i$ and measurement error
$\measnoise_i$. We use quadratic control costs~\cite{astrom97} to measure
the quality of a control application and its implementation.
This includes a cost for
the error in the plant state and the cost of changing the control
signals to achieve a certain state error (the latter cost can be
related to the amount of energy spent by the actuators).
Specifically, the quality of a controller for plant $\plant_i$
is given by the quadratic cost\newnot{symbol:controlcosti}
\begin{equation}
%  \setlength{\abovedisplayskip}{0ex}
%  \setlength{\belowdisplayskip}{0ex}
  \controlcost_i = \lim_{T \rightarrow \infty} \frac{1}{T}
  \expectedvalue{
    \int_0^T \transpose{\left[
      \begin{array}{c}\plantstate_i\\\plantinput_i\end{array}\right]} Q_i 
    \left[ \begin{array}{c}\plantstate_i\\\plantinput_i\end{array}\right] dt
  }.
  \label{prel:eq:controlcost}
\end{equation}
This stationary cost indicates the ability of the controller to reduce
the disturbances in the system (i.e., to have a small control error)
relative to the magnitude of the control signal (i.e., the amount of
spent control energy). The cost $\controlcost_i$ is decided partly by
the controller period and the control law $\plantinput_i$. The weight
matrix~$Q_i$ is a positive semi-definite matrix (usually a diagonal
matrix) that is used by the designer to assign weights to the
individual components of the state $\plantstate_i$ and the inputs
$\plantinput_i$ ($\expectedvalue{\cdot}$ denotes the expected value of
a stochastic variable).  The weight of a state, which is given by the
corresponding position in the matrix $Q_i$, indicates the importance
of a small variance in the state relative to the other states.  The
controlled inputs are also given weights by appropriate elements in
$Q_i$. In this way, the designer can indicate the desired trade-off
between the state cost and a small variance in the controlled input.

For the example with the inverted pendulums
(\Sectionref{prel:sec:plantmodel}), a possible weight matrix is
\begin{displaymath}
  Q_i = \textrm{diag}\left(\transpose{C_i} C_i, 0.002 \right) = 
  \left[
  \begin{array}{ccc}
    1 & 0 & 0 \\
    0 & 0 & 0 \\
    0 & 0 & 0.002 \\
  \end{array}
  \right].
\end{displaymath}
This indicates the importance of having a control that achieves small
variance in the pendulum position. The last element (0.002) indicates
that it is also of some importance to have small variance in the
controlled input (e.g., because of energy consumption in changing the
value of the input), however with less importance than the pendulum
state. For systems with several control loops, the matrix $Q_i$ can
also be used to transform the cost to a common baseline or to indicate
importance relative to other control loops. 

The quadratic cost in Equation~\ref{prel:eq:controlcost} is a very
common performance metric in the literature of control
systems~\cite{astrom97}. Note that a small control cost
$\controlcost_i$ indicates high control performance, and vice
versa. The control cost is a function of the sampling period of the
controller, the control law, and the characteristics of the delay
between sampling and actuation. As we have discussed, this delay is
complex and is induced not only by the computations and communications
of the controller but also, and more important, by the interference
experienced due to computation and communication delays of other tasks
and messages on the platform. To compute the cost $\controlcost_i$ for
the examples and experimental results presented in this thesis, the
Jitterbug toolbox~\cite{cervin02jitterbug, cervincontroltiming, jitterbugmanual} has
been used with the controller and characteristics of the
sampling--actuation delay as inputs.



\subsection{Controller Synthesis}
The synthesis of a controller for a plant $\plant_i$ comprises the
determination of the sampling period $\period_i$ and the control law
$\plantinput_i$.  The period $\period_i$ decides the rate of execution
of the tasks that implement the control law. This period is typically
decided based on the dynamics of the plant and the available
resources, as well as trade-offs between the control performance and
the performance of other applications running on the same execution
platform.  The control law determines how the sampled plant output is
used to compute the control signal to be applied to the plant through
actuator interfaces.

For a given sampling period $\period_i$ and a given constant
sensor--actuator delay $\delay_i^\textrm{sa}$\newnot{symbol:SAdelay}
(i.e., the time between sampling the output $\plantoutput_i$ and
updating the controlled input $\plantinput_i$), it is possible to find
the control law $\plantinput_i$ that minimizes the control cost
$\controlcost_i$~\cite{astrom97}.  Thus, optimal delay compensation
can be achieved if the delay of a certain control application is
constant. It is, in general, difficult to synthesize an optimal
control law for the case of varying delays in the control loop. 
\cbstart
As mentioned earlier, 
for those cases when an optimal controller can be synthesized, the control
law is typically time varying and complicated to implement (e.g., time
stamps may be required to find optimal delay compensation laws at
runtime).
A recent feature in the Jitterbug toolbox makes it possible
to design a control law that is optimal for a given constant delay
with a certain built-in robustness against given delay variations.

The control-design command in Jitterbug~\cite{jitterbugmanual}
produces a controller with the same structure as depicted
in Figure~\ref{prel:fig:controllerblockdiag}.
The controller is given by the following equations~\cite{jitterbugmanual}:
\begin{align}
  \plantinput[k] &= -L \estimate{\plantstate}_e[k \, | \, k] \label{prel:eq:statefeedback} \\
  \estimate{\plantstate}_e[k \, | \, k] &= \estimate{\plantstate}_e[k \, | \, k-1] + K_f\left( \plantoutput[k] - C_e \estimate{\plantstate}_e[k \, | \, k-1] \right) \label{prel:eq:estimatecorrection} \\
  \estimate{\plantstate}_e[k+1 \, | \, k] &= \Phi_e \estimate{\plantstate}_e[k \, | \, k-1] + \Gamma_e  \plantinput[k] \notag \\
  &+
  K\left( \plantoutput[k] - C_e \estimate{\plantstate}_e[k \, | \, k-1] \right) \label{prel:eq:estimatestate}
\end{align}
The observer state vector $\estimate{\plantstate}_e$
combines an estimate of the plant state and the previous 
control signals as defined by
\begin{displaymath}
\estimate{\plantstate}_e[k] = \left[ \begin{array}{c}
    \estimate{\plantstate}[k] \\
    \plantinput[k-1] \\
    \vdots \\
    \plantinput[k-\ell]
\end{array}
\right],
\end{displaymath}
where
\begin{displaymath}
\ell = \max \left( 1, \ceil{\frac{\delay^\textrm{sa}}{\period}} \right).
\end{displaymath}
As we have already mentioned, the period
$\period$ and constant sampling--actuation delay $\delay^\textrm{sa}$
are given as inputs to the control-law synthesis procedure.
In Equations~\ref{prel:eq:statefeedback}--\ref{prel:eq:estimatestate},
we use the notation
$[\,\cdot\,]$ to denote the value of a variable at a certain sampling
instant. For example, $\plantoutput[k]$ denotes the output of the
plant at the $k^\textrm{th}$ sampling instant, whereas $\plantinput[k]$ denotes
the controlled input at actuation $k$.
The notation $\estimate{\plantstate}_e[k \, | \, k-1]$ means the estimate of the plant state
at sampling instant $k$, when computed at sampling instant $k-1$.
At a certain sampling instant $k$, the controller measures the output
$\plantoutput[k]$ and uses it to compute an estimate $\estimate{\plantstate}_e[k \, | \, k]$
of the plant state at the current sampling instant (Equation~\ref{prel:eq:estimatecorrection}).
This computation is also based on an estimate $\estimate{\plantstate}_e[k \, | \, k-1]$
of the current state for which the estimation was performed at the previous 
sampling instant (Equation~\ref{prel:eq:estimatestate}). Following that,
the controlled input $\plantinput[k]$ to be actuated
is computed according to Equation~\ref{prel:eq:statefeedback}.
Last, the state at the next sampling instant $k+1$ is estimated according to
Equation~\ref{prel:eq:estimatestate}.
The parameters $L$, $K_f$, $K$, $C_e$, $\Phi_e$, and $\Gamma_e$ in 
Equations~\ref{prel:eq:statefeedback}--\ref{prel:eq:estimatestate} are outputs of 
the controller synthesis and are optimized for the given period and 
constant sensor--actuator delay.
\cbend


The quality of a controller is degraded (its cost $\controlcost_i$ is
increased) if the sensor--actuator delay is different from what was
assumed during the control-law synthesis, or if this delay is not
constant (i.e., there is jitter).  Considering that the
sensor--actuator delay is represented as a stochastic
variable $\DelaySA_i$\newnot{symbol:stochdelaySA} with probability
function $\DelaySApdf_{\Delay_i}$\newnot{symbol:pdfdelaySA}, we can
compute the cost~$\controlcost_i$ with the Jitterbug
toolbox~\cite{cervin02jitterbug}.  This is done for the cost
computations related to the results presented in this thesis. The
delay characteristics of the system depend on the scheduling policy
and communication protocol, as well as their parameters and
configuration. Optimization of scheduling and communication with
regard to control delays and performance of multiple distributed
control applications is the subject of Chapter~\ref{chap:distributed}.






\section{System Model} \label{prel:sec:sysmodel}
This section contains models and notation for the execution platform
and their running control applications. We shall also discuss mapping
and scheduling of the tasks and messages in the system.

\subsection{Platform Model} 
The control applications execute on a distributed execution platform
with multiple computation nodes that communicate on a bus. The
computation nodes, which are also called electronic control units in
the automotive domain, have input--output interfaces to the sensors
and actuators of the controlled plants. In addition, a computation
node comprises a CPU, several memories (e.g., RAM or ROM memories), an
operating system, and a communication controller. The operating system
implements a scheduling policy (e.g., static cyclic scheduling or priority-based
scheduling) for the executions on the CPU. The communication of
messages between computation nodes is conducted by the communication
controllers according to a certain communication protocol (e.g.,
TTP~\cite{kopetz97}, FlexRay~\cite{FlexRayspec}, or
CAN~\cite{CANspec}). Let us denote the set of computation nodes with
$\nodeset$\newnot{symbol:nodeset} and its index set with
$\indexset_\nodeset$\newnot{symbol:indexsetnodeset}.
\Figref{prel:fig:motivationalexample} shows two computation nodes
($\nodeset = \{\node_1,\node_2\}$) that are connected to a bus (the
communication controllers are denoted CC).  The figure also shows that
the computation nodes are connected to sensors and actuators. The
nodes have input--output interfaces that are used by the control
applications to measure and read plant outputs, and to write control
signals to actuators.

\begin{figure}
  \centering
  \includegraphics[width=0.7\textwidth]{controlscheduling/figures/figs/motivational_example}
  \caption[Example of an execution platform]{Example of an execution platform. Two computation nodes
    transmit and receive messages on the bus through the communication
    controllers (CC). Two control applications, comprising three tasks
    each, execute on the two nodes.}
  \label{prel:fig:motivationalexample}
\end{figure}


\subsection{Application Model}
The applications that execute and communicate on the distributed
platform comprise a set of tasks and messages. Let us denote the set
of all applications with
$\applicationset$\newnot{symbol:applicationset}.  Each application
represents the controller of a certain plant. We shall use the set
$\indexset_\plants$---the same index set as for the set of plants
$\plants$---to index applications in $\applicationset$. Thus,
application $\application_i$ is the controller for plant
$\plant_i$ ($i \in \indexset_\plants$).
An application $\application_i \in
\applicationset$\newnot{symbol:applicationi}
is modeled as a directed acyclic graph
\begin{displaymath}
\application_i = (\taskset_i,\msgset_i).
\end{displaymath}
\cbstart
The vertices in the set $\taskset_i$\newnot{symbol:taskseti}, which
are indexed by $\indexset_i$\newnot{symbol:indexsettaskseti},
represent computation tasks, whereas the edges in the set $\msgset_i
\subset \taskset_i \times \taskset_i$\newnot{symbol:msgseti} represent
messages between tasks (data dependencies). 
\cbend
We also introduce the set
of all tasks in the system as\newnot{symbol:alltasks}
\begin{displaymath}
\taskset_\applicationset = \bigcup_{i \in
  \indexset_\plants} \taskset_i.
\end{displaymath}
The specification of an application as a set of tasks is based on the
structure of the application and its different types of
computations. In \Figref{prel:fig:motivationalexample}, we show two
applications~$\applicationset = \{\application_1,\application_2\}$
($\indexset_\plants = \{1,2\}$), which are controllers for the two
pendulums~$\plant_1$ and~$\plant_2$ in the example in
Section~\ref{prel:sec:plantmodel}. For~$i \in \indexset_\plants$, the
task set of application~$\application_i$ is $\taskset_i = \{
\task_{is}, \task_{ic}, \task_{ia} \}$ with index set $\indexset_i =
\{s,c,a\}$.  For example, task $\task_{1s}$ on node $\node_1$ is the
sensor task that measures the position of the pendulum by reading and
processing data from the sensor. A message $\msg_{1sc}$ is sent on the
bus to node $\node_2$, whereafter the control task $\task_{1c}$
computes the control signal to be actuated. The actuation is done by
task $\task_{1a}$ on node $\node_1$, which is the only node connected
to the actuator of $\plant_1$.  An arbitrary task shall in the
continuation be denoted by $\task$.\newnot{symbol:task} A task of
application $\application_i$ is denoted
$\task_{ij}$,\newnot{symbol:taskij} where $i \in \indexset_\plants$
and $j \in \indexset_i$.  An arbitrary message between tasks
$\task_{ij}$ and $\task_{ik}$ in application $\application_i$ is
denoted $\msg_{ijk}$.\newnot{symbol:msgijk}


Each application $\application_i \in \applicationset$ has a period
$\period_i$,\newnot{symbol:periodi} which decides the rate of
execution of $\application_i$. Jobs of the application tasks are
released for execution periodically and are scheduled for execution
according to the scheduling policies of the computation nodes. Thus,
at time $(q-1)\period_i$, a job of each task in the application is
released for execution.  Job~$q$ of task~$\task_{ij}$ is
denoted~$\job{ij}{q}$\newnot{symbol:jobij} and is released at time
$(q-1)\period_i$.  For a message~$\msg_{ijk} = (\task_{ij},\task_{ik})
\in \msgset_i$, the message instance produced by job~$\job{ij}{q}$ is
denoted~$\msginstance{ijk}{q}$.\newnot{symbol:msginstijk} An
edge~$\msg_{ijk} = (\task_{ij},\task_{ik}) \in \msgset_i$ means that
the earliest start time of a job~$\job{ik}{q}$ is when~$\job{ij}{q}$
has completed its execution and the produced message instance
$\msginstance{ijk}{q}$ has been communicated to the computation node
that hosts task $\task_{ik}$. Let us also define the hyper period
$\hyperperiod$\newnot{symbol:hyperperiod} of all control applications
as the least common multiple of all application periods. Further, a
task can have a deadline, which means that any job of that task must
finish within a given time relative to its release. Control
applications do not typically have hard timing constraints, but
instead the goal is to achieve a certain level of control
quality. 
\cbstart
Additional tasks, representing other application domains
(e.g., safety-critical applications with strict timing constraints, or
best-effort applications), may coexist with the control applications
on the distributed execution platform.
\cbend

\subsection{Mapping and Scheduling} \label{prel:sec:mappingscheduling}
Each task in the system is mapped to a computation node. The mapping
is given by a function\newnot{symbol:mapping}
\begin{displaymath}
\mapping : 
\taskset_\applicationset \longrightarrow \nodeset
\end{displaymath}
that returns the computation node of a certain task in the system.
Typically, a certain task may be mapped only to a subset of the
computation nodes of the system. For example, tasks that read sensors
or write to actuators can only be mapped to computation nodes that
provide input--output interfaces to the needed sensors and actuators.
Also, some tasks may require specialized instructions or hardware
accelerators that are available only on some nodes in the platform.
To model such mapping constraints, we consider given a function\newnot{symbol:mappinglimitation}
\begin{displaymath}
\mappinglimitation :
\taskset_\applicationset \longrightarrow \powerset{\nodeset}
\end{displaymath}
that, for each task $\task \in \taskset_\applicationset$ in the
system, gives the set of computation nodes $\mappinglimitation(\task)
\subseteq \nodeset$ that task $\task$ can be mapped to.  We shall
treat mapping constraints further in Chapter~\ref{chap:faulttolerance}
for the remapping problem that arises as a consequence of failed
computation nodes. Let us proceed by introducing the function
\begin{displaymath}
\invmap : \nodeset \longrightarrow
\powerset{\taskset_\applicationset}
\end{displaymath}
that, for a certain node $\node_d$, returns the set of tasks that are mapped
to~$\node_d$. Thus, we have
\begin{displaymath}
  \invmap(\node_d) = \left\{ \task_{ij} \in
  \taskset_\applicationset :
  \mapping(\task_{ij}) = \node_d \right\}.
\end{displaymath}
A message between tasks mapped to different nodes is sent on the bus.
Thus, the set of messages that are communicated on the bus is
\begin{displaymath}
\msgset_\busindex =
\left\{ (\task_{ij},\task_{ik}) \in
\bigcup_{i \in \indexset_\plants} \msgset_i 
: \mapping(\task_{ij}) \neq \mapping(\task_{ik})
\right\}.
\end{displaymath}
For a message instance~$\msginstance{ijk}{q}$, we denote with
$\exectime_{ijk}$\newnot{symbol:commtimeijk} the communication time when there are no conflicts
on the bus.  For our example with the mapping in
\Figref{prel:fig:motivationalexample}, we note that the set of messages on
the bus is $\msgset_\busindex = \msgset_1 \cup \msgset_2$.  Given a
mapping of the tasks to the computation nodes, we have, for each task,
a specification of possible execution times during runtime. We model
the execution time of task $\task_{ij}$ as a stochastic variable
$\exectime_{ij}$ with probability 
function $\pdf_{\exectime_{ij}}$.\newnot{symbol:pdfexectimeij} It
is assumed that the execution time is bounded by given best-case and
worst-case execution times, denoted~$\bcet{ij}$\newnot{symbol:bcetij}
and $\wcet{ij}$\newnot{symbol:wcetij},
respectively. 
\cbstart
These properties are obtained with tools and methods for simulation, profiling,
and program analysis~\cite{wilhelm08}.
\cbend
In \Figref{prel:fig:motivationalexample}, the execution times (constant in
this example) and communication times for the tasks and messages are
given in milliseconds inside parentheses.


In this thesis, we consider systems with static cyclic scheduling or
priority-based scheduling of tasks and messages.  For static cyclic
scheduling, tasks are executed on each computation node according to
schedule tables that are constructed at design time. Similarly, the
communication controllers conduct the communication on the bus
according to tables with start times for the transmissions. An example
of such a statically scheduled system is the time-triggered
architecture with the TTP communication protocol~\cite{kopetz97}.
Examples of priority-based scheduling policies with static priorities
are rate-monotonic and deadline-monotonic scheduling, whereas the
earliest-deadline-first policy is a representative of a scheduling
algorithm with dynamic
priorities~\cite{liu73,buttazzo97,shin97,stankovic95}.  The most
prominent example of a communication protocol for priority-based
scheduling of messages is CAN~\cite{CANspec}. The design frameworks
that are proposed in this thesis support systems with static-cyclic
scheduling according to schedule tables and priority-based scheduling
with static priorities that are synthesized at design time. These
parameters related to scheduling and communication are synthesized at
design time and influence the delay characteristics (delay and jitter)
of the system at runtime. As we have discussed in
Section~\ref{prel:sec:controlperformance}, the delay is an important
and influential parameter that decides the control performance. Thus,
optimization of parameters related to scheduling and communication in
embedded control systems is an important design activity, in addition
to period selection and control-law synthesis. We shall in the
beginning of the next chapter motivate such optimizations with an example
(Section~\ref{distributed:sec:example}).
